/**
 * 规则： 将未排序的元素插入到已排序的元素中
 * 1、将序列分为已排序和未排序,将第一个元素归为已排序，其他归为未排序
 * 2、从未排序中依次取出元素，对比已排序的数据，将元素插入到合适的位置
 *      从已排序部分的末尾开始，逐个比较已排序部分的元素，找到合适的位置插入选定的元素，直到找到第一个不大于该元素的位置。
 */
function insertSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    let j = i - 1
    let key = arr[i]
    while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = key
  }
}
const arr = [4,5,2,1,3,7,6]
const a = insertSort(arr)
console.log(arr);

function inser(arr) {
  for(let i = 1; i < arr.length; i++) {
    let j = i - 1
    let val = arr[i]
    while(j >= 0 && val < arr[j]) {
      // 整体往后移一个位
      arr[j + 1] = arr[j]
      j--
    }
    // 第一个大于数的下标
    arr[j + 1] = val
  }

}